/*
 * @lc app=leetcode.cn id=2187 lang=typescript
 *
 * [2187] 完成旅途的最少时间
 */

// @lc code=start
function minimumTime(time: number[], totalTrips: number): number {
  // 使用 n 个时间可以完成多少趟旅程
  const isValidate = (n: number) => {
    let res = 0;
    for (const x of time) {
      res += Math.floor(n / x);
    }
    return res;
  };

  // 初始化二分查找区间
  let l = 0;
  let r = totalTrips * time[0];
  for (const x of time) {
    r = Math.min(r, totalTrips * x);
  }
  // 二分查找
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    if (isValidate(mid) < totalTrips) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }

  return l;
}
// @lc code=end
